﻿// 202 完全背包.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
http://oj.daimayuan.top/course/5/problem/162
有 n种物品要放到一个袋子里，袋子的总容量为 m，第 i种物品的体积为 vi，
把它放进袋子里会获得 wi的收益，每种物品能用无限多次，
问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。

输入格式
第一行两个整数 n,m。

接下来 n行，每行两个整数 vi,wi。 

输出格式
一个整数，表示答案。

样例输入
5 10
5 3
3 6
7 8
5 9
2 4
样例输出
20
数据规模
对于所有数据，保证 1≤n,m,vi,wi≤1000。
*/

const int N = 1010;
int v[N], w[N];
int dp[N];
int n, m;

int main()
{
	cin >> n >> m;

	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >=0 ; j--) {
			for (int k = 0; k * v[i] <= j; k++) {
				dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
			}
		}
	}

	cout << dp[m] << endl;

	return 0;
}

 